Boolean functions defined on pseudo-recursive sequences

Abstract: We define Boolean functions on hypergraphs with edges having big intersections, and an opposite situation, hypergraphs which are thinly intersective induced by pseudo-recursive sequences. As a main result, we estimate the cardinality of their supports. A sequence $X$ is said to be pseudo-recursive (or pesudo-linear) sequence if the identity $x_{n+1}=M\cdot x_n+ b_{j_{n+1}}$ holds, where $ b_{j_{n+1}}\in \{b_1,b_2, \dots b_k\}$) for $n \geq 0$ and $M$ is a positive integer. (This type of sequences have a long list in the combinatorial number theory and other areas too, e.g. in random walk theory).

The tools come from additive combinatorics and the uncertainty inequality.

number theory

Audience: researchers in the discipline

Combinatorial and additive number theory (CANT 2022)